package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.entity.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 给定一棵二叉树 root，返回所有重复的子树。
 * <p>
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 * <p>
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 */
public class Solution652 {

	//	Map<String, TreeNode> seen = new HashMap<String, TreeNode>();
	//	Set<TreeNode> repeat = new HashSet<TreeNode>();

	Map<String, Integer> map = new HashMap<String, Integer>();
	Set<TreeNode> result = new HashSet<TreeNode>();

	// 暴力对比
	public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
		dfs(root);
		return new ArrayList<TreeNode>(result);
	}

	public String dfs(TreeNode node) {
		if (node == null) {
			return "";
		}
		String left = dfs(node.left);
		String right = dfs(node.right);
		StringBuilder sb = new StringBuilder();
		sb.append(node.val);
		sb.append("_");
		sb.append(left);
		sb.append("_");
		sb.append(right);
		String key = sb.toString();
		map.put(key, map.getOrDefault(key, 0) + 1);
		if (map.get(key) == 2) {
			result.add(node);
		}
		return key;
	}

	public static void main(String[] args) {
		Solution652 solution652 = new Solution652();
		TreeNode node = new TreeNode();
		node.val = 2;
		solution652.findDuplicateSubtrees(node);
		System.out.println(solution652.result);
	}

}
